package com.wrial.kind.tree;
/*
 * @Author  Wrial
 * @Date Created in 17:46 2020/8/8
  * @Description 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值
 *      输入: [1,2,3,null,5,null,4]
        输出: [1, 3, 4]
        解释:

           1            <---
         /   \
        2     3         <---
         \     \
          5     4       <---

 */

import java.util.ArrayList;
import java.util.List;

public class RightSideView {
    /**
     * 两种方式：
     * DFS和BFS
     * 1.DFS  因为是右视图，所有就得按照 根 右 左的顺序来
     * 时间复杂度为O(N) 每个节点都访问了一次  空间复杂度为O(logN)-O(N)  到O(N)是链表了
     * 2.BFS  每次层次遍历的最后一个节点即为每层的右视图
     * 时间复杂度 O(N) 空间复杂度O(N) 每个节点都放入队列一次
     *
     * @param root
     * @return
     */
    int level = 0; //代表当前需要第几层的右1节点  根level为0
    List<Integer> ans = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root,0);
        return ans;
    }

    private void dfs(TreeNode root, int depth) {
        if (root==null) return;
        if (level==depth){  //说名是当前层第一个节点
            ans.add(root.val);
            level++;        //此时level也就等于ans.size
        }
        dfs(root.right, depth+1);
        dfs(root.left, depth+1);
    }

    public class TreeNode {
        int val;
         TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
